﻿#include "SortingAlgorithm.h"

#include <QDebug>

namespace GeneralAlgorithm {

	SortingAlgorithm::SortingAlgorithm(QObject *parent)
		: QObject(parent)
	{

	}

	SortingAlgorithm::~SortingAlgorithm()
	{

	}

	void SortingAlgorithm::bubbleSortAlgorithm(int arr[], int size)
	{
		if (size < 0)
		{
			return;
		}

		for (int i = 0; i< size - 1; i++)
		{
			for (int j = 0; j< size - i - 1; j++)
			{
				if (arr[j] > arr[j + 1])		 // 相邻元素两两对比
				{
					int temp = arr[j];			  // 元素交换
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}
	}

	void SortingAlgorithm::selectionSortAlgorithm(int arr[], int len)
	{
		for (int i = 0; i < len; i++)
		{
			int min = i;
			for (int j = i + 1; j < len; j++)
			{
				if (arr[j] < arr[min])
					min = j;
			}
			int temp = arr[min];
			arr[min] = arr[i];
			arr[i] = temp;
		}
	}

	void SortingAlgorithm::InsertionSortAlgorithm(int arr[], int len)
	{
		for (int i = 1; i < len; i++)				//第一个元素作为基准元素，从第二个元素开始把其插到正确的位置
		{
			if (arr[i] < arr[i - 1])				//如果第i个元素比前面的元素小
			{
				int j = i - 1;						//需要判断第i个元素与前面的多个元素的大小，换成j继续判断
				int x = arr[i];						//将第i个元素复制为哨兵
				while (j >= 0 && x < arr[j])		//找哨兵的正确位置，比哨兵大的元素依次后移
				{
					arr[j + 1] = arr[j];
					j--;
				}
				arr[j + 1] = x;						//把哨兵插入到正确的位置
			}
		}
	}

	void SortingAlgorithm::ShellSortAlgorithm(int arr[], int len)
	{
		int i, j, gap;   // gap为步长，每次减为原来的一半。
		for (gap = len / 2; gap > 0; gap /= 2)
		{
			// 共gap个组，对每一组都执行直接插入排序
			for (i = 0; i < gap; i++)
			{
				for (j = i + gap; j < len; j += gap)
				{
					// 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。
					if (arr[j] < arr[j - gap])
					{
						int tmp = arr[j];
						int k = j - gap;
						while (k >= 0 && arr[k] > tmp)
						{
							arr[k + gap] = arr[k];
							k -= gap;
						}
						arr[k + gap] = tmp;
					}
				}
			}
		}
	}

}// namespace GeneralAlgorithm